package dataStructure;

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

import algorithms.Algo;

public class DicHashTreeNode implements INode {

	public ItemSet set;
	public int depth;
	public HashMap<String, DicHashTreeNode> childrens;
	public TreeSet<String> frequentChildrens;
	public DicHashTreeNode parent;
	public String keyAtPArent;
	boolean updatedParent;
	long discoveryIndex;// Equals to iteration_number * basket_index
	long lastEncounterdIndex = 0;

	public DicHashTreeNode(int _depth, long _discIndex) {
		childrens = new HashMap<String, DicHashTreeNode>();
		depth = _depth;
		discoveryIndex = _discIndex;
		updatedParent = false;
		frequentChildrens = new TreeSet<String>();
	}

	public boolean pruneAtDepth(int absSupport, int numOfBaskets,
			int pruneDepth, long basketIndex) {

		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		boolean alive = false;// There are still live itemsets of size
		// $pruneDepth

		Iterator<String> iter1 = childrens.keySet().iterator();
		DicHashTreeNode node;
		String key;

		// Prune or find the correct depth
		while (iter1.hasNext()) {
			key = iter1.next();
			node = childrens.get(key);
			if (node.pruneCondition(absSupport, numOfBaskets, basketIndex)) {
				iter1.remove();
			} else
				alive = true;
		}
		if (depth < pruneDepth - 1) {
			while (iter1.hasNext()) {
				key = iter1.next();
				if (childrens.get(key).pruneAtDepth(absSupport, numOfBaskets,
						pruneDepth, basketIndex))
					alive = true;
			}
		}
		return alive;
	}

	public boolean pruneChildrens(int absSupport) {
		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		boolean alive = false;// There are still live itemsets of size
		// $pruneDepth

		Iterator<String> iter1 = childrens.keySet().iterator();
		DicHashTreeNode node;
		String key;

		HashMap<String, DicHashTreeNode> frequentChilderens = null;
		frequentChilderens = new HashMap<String, DicHashTreeNode>();
		while (iter1.hasNext()) {
			key = iter1.next();
			node = childrens.get(key);
			if (node.isFrequent(absSupport)) {
				Algo.incStats(1);
				frequentChilderens.put(key, node);
				alive = true;
			}
		}
		childrens.clear();
		childrens = frequentChilderens;
		return alive;
	}

	public boolean discoverTillDepth(int absSupport, int numOfBaskets,
			int discoverDepth, long basketIndex) {

		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		DicHashTreeNode node;
		ItemSet newIS;
		String key;
		boolean foundNewItemset = false;

		// Discover or find the correct depth
		{
			Iterator<String> ascIter = frequentChildrens.iterator();
			Iterator<String> desIter;
			String key1, key2;
			DicHashTreeNode node1, node2;
			DicHashTreeNode newNode;
			while (ascIter.hasNext()) {
				key1 = ascIter.next();
				node1 = childrens.get(key1);
				if (node1 == null || !node1.isFrequent(absSupport))
					continue;
				desIter = frequentChildrens.descendingIterator();
				while (desIter.hasNext()) {
					key2 = desIter.next();

					if (key2.equals(key1))
						break;

					// Maybe this was discovered before
					if (node1.childrens.containsKey(key2))
						continue;

					node2 = childrens.get(key2);
					if (node2 == null || !node2.isFrequent(absSupport))
						continue;

					foundNewItemset = true;
					Algo.incStats(node1.depth + 1);

					// Two good candidates - merge them!
					newIS = new ItemSet();
					for (String item : node1.set) {
						newIS.addItem(item);
					}
					newIS.addItem(key2);// node2.set.getLast()==key2
					newNode = new DicHashTreeNode(node1.depth + 1, basketIndex);
					newIS.counter = 0;
					newNode.set = newIS;
					newNode.parent = node1;
					newNode.keyAtPArent = key2;
					node1.put(key2, newNode);
				}
			}
		}
		if (depth < discoverDepth - 1) {
			Iterator<String> iter1 = childrens.keySet().iterator();
			while (iter1.hasNext()) {
				key = iter1.next();
				node = childrens.get(key);
				// We don't discover not frequent subtrees
				// The null case is just for the root...
				if (node.set == null || node.isFrequent(absSupport)) {
					if (childrens.get(key).discoverTillDepth(absSupport,
							numOfBaskets, discoverDepth, basketIndex))
						foundNewItemset = true;
				}
			}
		}
		return foundNewItemset;
	}

	public boolean discoverChildrens(int absSupport, long basketIndex) {
		boolean foundNewItemset = false;
		ItemSet newIS;

		TreeSet<String> sortedChildrensKeys = new TreeSet<String>();
		for (String child : childrens.keySet()) {
			sortedChildrensKeys.add(child);
		}

		Iterator<String> ascIter = sortedChildrensKeys.iterator();
		Iterator<String> desIter;
		String key1, key2;
		DicHashTreeNode node1, node2;
		DicHashTreeNode newNode;
		while (ascIter.hasNext()) {
			key1 = ascIter.next();
			node1 = childrens.get(key1);
			if (!node1.isFrequent(absSupport))
				continue;
			desIter = sortedChildrensKeys.descendingIterator();
			while (desIter.hasNext()) {
				key2 = desIter.next();
				if (key2.equals(key1))
					break;
				node2 = childrens.get(key2);
				if (!node2.isFrequent(absSupport))
					continue;

				foundNewItemset = true;
				Algo.incStats(depth + 1);

				// Two good candidates - merge them!
				newIS = new ItemSet();
				for (String item : node1.set) {
					newIS.addItem(item);
				}
				newIS.addItem(key2);// node2.set.getLast()==key2
				newNode = new DicHashTreeNode(depth + 1, basketIndex);
				newNode.set = newIS;
				node1.put(key2, newNode);
			}
		}
		return foundNewItemset;
	}

	/***
	 * Check if this subtree is ready for pruning
	 * 
	 * @return true iff we should prune this sub tree
	 */
	boolean pruneCondition(int absSupport, int numOfBaskets, long basketIndex) {
		return !isFrequent(absSupport)
				&& basketIndex >= discoveryIndex + numOfBaskets;
	}

	boolean isFrequent(int absSupport) {
		return set.counter > absSupport * (depth == 1 ? 1 : 0.5);
	}

	public void put(String key, DicHashTreeNode child) {
		childrens.put(key, child);
		// sortedChildrensKeys.add(key);
	}

	/***
	 * We count a node only if this is the first time we count it for a given
	 * basket That means that we will conut it only for baskets which appears in
	 * the next $numOfBaskets from its discovery
	 * 
	 * @param basketIndex
	 * @param iterationNumber
	 * @param numOfBaskets
	 */
	public void encounterNode(long basketIndex, int numOfBaskets, int support) {
		if (basketIndex >= discoveryIndex + numOfBaskets)
			return;

		if (lastEncounterdIndex != 0 && basketIndex == lastEncounterdIndex)
			return;

		lastEncounterdIndex = basketIndex;

		set.counter++;
		if (!updatedParent && set.counter > support) {
			updatedParent = true;
			if (parent == null || parent.frequentChildrens == null)
				return;
			parent.frequentChildrens.add(keyAtPArent);
		}
	}

	@Override
	public int getNumOfChildrens() {
		return childrens.size();
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if (set != null)
			sb.append(set.toString());
		if (childrens != null) {
			for (String key : childrens.keySet()) {
				sb.append(childrens.get(key).toString());
			}
		}
		return sb.toString();
	}

	public String toString(int support) {
		if (set != null && set.counter < support)
			return "";
		StringBuilder sb = new StringBuilder();
		if (set != null)
			sb.append(set.toString());
		if (childrens != null) {
			for (String key : childrens.keySet()) {
				sb.append(childrens.get(key).toString(support));
			}
		}
		return sb.toString();
	}
}